{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Index of the Large Integer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #interactive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #交互"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getIndex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到最大整数的索引"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们有这样一个整数数组&nbsp;<code>arr</code>&nbsp;，除了一个最大的整数外，其他所有整数都相等。你不能直接访问该数组，你需要通过&nbsp;<strong>API</strong> <code>ArrayReader</code>&nbsp;来间接访问，这个 API&nbsp;有以下成员函数：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>int compareSub(int l, int r, int x, int y)</code>：其中&nbsp;<code>0 &lt;= l, r, x, y &lt;&nbsp;ArrayReader.length()</code>，&nbsp;<code>l &lt;= r</code>&nbsp;且&nbsp;<code>x &lt;= y</code>。这个函数比较子数组&nbsp;<code>arr[l..r]</code>&nbsp;与子数组&nbsp;<code>arr[x..y]</code>&nbsp;的和。该函数返回：\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li><strong>1</strong>&nbsp;若&nbsp;<code>arr[l]+arr[l+1]+...+arr[r] &gt; arr[x]+arr[x+1]+...+arr[y]</code>&nbsp;。</li>\n",
    "\t\t<li><strong>0</strong>&nbsp;若&nbsp;<code>arr[l]+arr[l+1]+...+arr[r] == arr[x]+arr[x+1]+...+arr[y]</code>&nbsp;。</li>\n",
    "\t\t<li><strong>-1</strong>&nbsp;若&nbsp;<code>arr[l]+arr[l+1]+...+arr[r] &lt; arr[x]+arr[x+1]+...+arr[y]</code>&nbsp;。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li><code>int length()</code>：返回数组的长度。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你最多可以调用函数&nbsp;<code>compareSub()</code>&nbsp;<strong>20 次</strong>。你可以认为这两个函数的时间复杂度都为&nbsp;<code>O(1)</code>&nbsp;。</p>\n",
    "\n",
    "<p>返回<em>&nbsp;<code>arr</code>&nbsp;中最大整数的索引。</em></p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> arr = [7,7,7,7,10,7,7,7]\n",
    "<strong>输出:</strong> 4\n",
    "<strong>解释:</strong> API 的调用如下：\n",
    "reader.compareSub(0, 0, 1, 1) // 返回 0。比较子数组 (0, 0) 与子数组 (1, 1) （即比较 arr[0] 和 arr[1]）。\n",
    "因此我们知道 arr[0] 和 arr[1] 不包含最大元素。\n",
    "reader.compareSub(2, 2, 3, 3) // 返回 0。我们可以排除 arr[2] 和 arr[3]。\n",
    "reader.compareSub(4, 4, 5, 5) // 返回 1。因此，可以确定 arr[4] 是数组中最大的元素。\n",
    "注意，我们只调用了 3 次 compareSub，所以这个答案是有效的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [6,6,12]\n",
    "<strong>输出:</strong> 2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= arr.length&nbsp;&lt;= 5 * 10^5</code></li>\n",
    "\t<li><code>1 &lt;= arr[i] &lt;= 100</code></li>\n",
    "\t<li><code>arr</code>&nbsp;中除一个最大元素外，其余所有元素都相等。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果&nbsp;<code>arr</code>&nbsp;中有两个整数比其他数大呢？</li>\n",
    "\t<li>如果有一个数比其他数大，另一个数比其他数小呢？</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-index-of-the-large-integer](https://leetcode.cn/problems/find-the-index-of-the-large-integer/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-index-of-the-large-integer](https://leetcode.cn/problems/find-the-index-of-the-large-integer/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[7,7,7,7,10,7,7,7]', '[6,6,12]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        l, r = 0, n - 1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            IsOdd = (r - l + 1) % 2 == 1\n",
    "            if IsOdd:  #区间长度为奇数\n",
    "                ans = reader.compareSub(l, mid, mid, r)\n",
    "            else:\n",
    "                ans = reader.compareSub(l, mid, mid + 1, r)\n",
    "            if ans == 0:\n",
    "                return mid\n",
    "            elif ans > 0:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        length = reader.length()\n",
    "        left = 0\n",
    "        right = length - 1\n",
    "        comp = 0\n",
    "        while length > 0:\n",
    "            length = right - left + 1\n",
    "            half = length //2\n",
    "            if length % 2 == 0:\n",
    "                comp = 1\n",
    "            else: \n",
    "                comp = 0\n",
    "\n",
    "            temp = reader.compareSub(left, left + half - comp, left + half, right)\n",
    "            if temp == 0:\n",
    "                return left + half - comp\n",
    "            elif temp == 1:\n",
    "                right = left + half - comp\n",
    "            else:\n",
    "                left = left + half\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        l, r = 0, reader.length() - 1\n",
    "        while l < r:\n",
    "            mid = (l + r) >> 1\n",
    "            if mid - l == r - mid:\n",
    "                res = reader.compareSub(l, mid - 1, mid + 1, r)\n",
    "                if res == 0:\n",
    "                    return mid\n",
    "                elif res > 0:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            else:\n",
    "                if reader.compareSub(l, mid, mid + 1, r) > 0:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        l,r = 0, reader.length()-1\n",
    "        while l < r:\n",
    "            mid = (l+r)>>1\n",
    "            if (r-l+1)&1:\n",
    "                comp = reader.compareSub(l, mid-1, mid+1, r)\n",
    "                if comp == 1:\n",
    "                    r = mid - 1\n",
    "                elif comp == 0:\n",
    "                    return mid \n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            else:\n",
    "                comp = reader.compareSub(l, mid, mid+1, r)\n",
    "                if comp == 1:\n",
    "                    r = mid \n",
    "                else:\n",
    "                    l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        # 二分查找\n",
    "        l, r = 0, reader.length()-1\n",
    "        mid = (l+r)//2\n",
    "        while l<r:\n",
    "            if r-mid==mid-l:\n",
    "                flg = reader.compareSub(l,mid,mid,r)\n",
    "            else:\n",
    "                flg = reader.compareSub(l,mid,mid+1,r)\n",
    "            if r-mid==mid-l and flg==0:\n",
    "                return mid\n",
    "            elif flg==1:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid+1\n",
    "            mid = (l+r)//2\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        left, right = 0, reader.length() - 1\n",
    "        while left < right:\n",
    "            middle = (left + right) // 2\n",
    "            if (right - left) % 2 == 0:\n",
    "                temp = reader.compareSub(left, middle, middle, right)\n",
    "                if temp == 1:\n",
    "                    right = middle\n",
    "                elif temp == -1:\n",
    "                    left = middle\n",
    "                else:\n",
    "                    return middle\n",
    "            else:\n",
    "                temp = reader.compareSub(left, middle, middle + 1, right)\n",
    "                if temp == 1:\n",
    "                    right = middle\n",
    "                elif temp == -1:\n",
    "                    left = middle + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n=reader.length()\n",
    "        left,right=0,reader.length()-1  \n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            if (right-left+1)%2==0:\n",
    "                if reader.compareSub(left,mid,mid+1,right)==1:\n",
    "                    right=mid\n",
    "                else:\n",
    "                    left=mid+1\n",
    "            else:\n",
    "                if reader.compareSub(left,mid,mid,right)==1:\n",
    "                    right=mid\n",
    "                else:\n",
    "                    left=mid\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        l,r = 0, reader.length()-1\n",
    "        while l < r:\n",
    "            mid = (l+r)>>1\n",
    "            is_odd = (r-l+1)&1 == 1\n",
    "            if is_odd:\n",
    "                comp = reader.compareSub(l, mid-1, mid+1, r)\n",
    "                if comp == 1:\n",
    "                    r = mid - 1\n",
    "                elif comp == 0:\n",
    "                    return mid \n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            else:\n",
    "                comp = reader.compareSub(l, mid, mid+1, r)\n",
    "                if comp == 1:\n",
    "                    r = mid \n",
    "                else:\n",
    "                    l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        low = 0\n",
    "        high = n - 1\n",
    "        while low < high:\n",
    "            mid = low + (high - low) // 2\n",
    "            if 2 * mid != high + low:\n",
    "                score = reader.compareSub(low, mid, mid+1, high)\n",
    "                if score == 1:\n",
    "                    high = mid\n",
    "                else:\n",
    "                    low = mid + 1\n",
    "            else:\n",
    "                score = reader.compareSub(low, mid-1, mid+1, high)\n",
    "                if score == 1:\n",
    "                    high = mid - 1\n",
    "                elif score == 0:\n",
    "                    return mid\n",
    "                else:\n",
    "                    low = mid + 1\n",
    "        return low\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        l, r = 0, reader.length() - 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if (l + r + 1) % 2 == 1:#数组长度为奇数\n",
    "                if reader.compareSub(l, mid, mid, r) >= 0:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid\n",
    "            else:#数组长度为偶数\n",
    "                if reader.compareSub(l, mid, mid + 1, r) >= 0:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        l,r = 0, reader.length()-1\n",
    "        while l < r:\n",
    "            mid = (l+r)>>1\n",
    "            if (r-l+1)&1:\n",
    "                comp = reader.compareSub(l, mid-1, mid+1, r)\n",
    "                if comp == 1:\n",
    "                    r = mid - 1\n",
    "                elif comp == 0:\n",
    "                    return mid \n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            else:\n",
    "                comp = reader.compareSub(l, mid, mid+1, r)\n",
    "                if comp == 1:\n",
    "                    r = mid \n",
    "                else:\n",
    "                    l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        L = 0               #实指\n",
    "        R = n - 1           #实指\n",
    "        while L < R :\n",
    "            mid = L + R >> 1\n",
    "            #-------------- 奇数个，L=0 [0 1 2] mid=3 [3 4 5 6] R=6\n",
    "            if (R - L) % 2 == 0:\n",
    "                #比较 [0 1 2] 和 [4 5 6]\n",
    "                check = reader.compareSub(L, mid - 1, mid + 1 , R)\n",
    "                #-- 左边大，在左\n",
    "                if check == 1:\n",
    "                    R = mid - 1     #左半的R界为mid=2\n",
    "                #-- 右边大，在右\n",
    "                elif check == -1:\n",
    "                    L = mid + 1     #右半的L界为4\n",
    "                #-- 两边一样大\n",
    "                else:\n",
    "                    return mid\n",
    "\n",
    "            #--------------偶数个，L=0 [0 1 2] mid=2 [3 4 5] R=5\n",
    "            else:\n",
    "                #-- 比较 [0 1 2] 和 [3 4 5]\n",
    "                check = reader.compareSub(L, mid, mid + 1, R)\n",
    "                #-- 左边大，在左\n",
    "                if check == 1:\n",
    "                    R = mid         #左半的R界为2\n",
    "                #-- 右边大，在右\n",
    "                elif check == -1:\n",
    "                    L = mid + 1     #右半的L界为3\n",
    "                #-- 两边一样大，不存在\n",
    "                else:\n",
    "                    return -1\n",
    "        return L\n",
    "\n",
    "# 作者：HanXin\n",
    "# 链接：https://leetcode.cn/problems/find-the-index-of-the-large-integer/solutions/745539/cpython3-er-fen-cha-zhao-jin-jie-2ge-qu-u0ped/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        l, r = 0, n - 1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            IsOdd = (r - l + 1) % 2 == 1\n",
    "            if IsOdd:  #区间长度为奇数\n",
    "                ans = reader.compareSub(l, mid, mid, r)\n",
    "            else:\n",
    "                ans = reader.compareSub(l, mid, mid + 1, r)\n",
    "            if ans == 0:\n",
    "                return mid\n",
    "            elif ans > 0:\n",
    "                r = mid - 1 if IsOdd else mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        left,right = 0,n-1\n",
    "        mid = 0\n",
    "        temp = 0\n",
    "        while(left<right):\n",
    "            mid = left+(right-left)//2\n",
    "            if (right - left+1)%2!=0:\n",
    "                temp = reader.compareSub(left,mid,mid,right)\n",
    "            else:\n",
    "                temp = reader.compareSub(left,mid,mid+1,right)\n",
    "            if temp==1:\n",
    "                right = mid\n",
    "            elif temp==0:\n",
    "                return mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "# my：二分（refer 网友）\n",
    "# class Solution:\n",
    "#     def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "#         n=reader.length()\n",
    "#         l,r=0,n-1\n",
    "#         while l<r:\n",
    "#             mid=(l+r)//2\n",
    "#             if (r+1-l)%2:### 分奇偶来确定二分左右区间边界\n",
    "#                 ll,rr,x,y=l,mid-1,mid+1,r \n",
    "#             else:\n",
    "#                 ll,rr,x,y=l,mid,mid+1,r\n",
    "#             cmp=reader.compareSub(ll,rr,x,y)\n",
    "#             if (r+1-l)%2 and cmp==0:\n",
    "#                 return mid \n",
    "#             elif cmp==1:\n",
    "#                 r=rr    \n",
    "#             elif cmp==-1:\n",
    "#                 l=x \n",
    "#         return l\n",
    "\n",
    "\n",
    "# \"\"\"\n",
    "\n",
    "# This is ArrayReader's API interface.\n",
    "\n",
    "# You should not implement it, or speculate about its implementation\n",
    "\n",
    "# \"\"\"\n",
    "\n",
    "#class ArrayReader(object):\n",
    "\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "\n",
    "#\n",
    "\n",
    "#\t # Returns the length of the array\n",
    "\n",
    "#    def length(self) -> int:\n",
    "\n",
    "#\n",
    "\n",
    "\n",
    "### 网：二分\n",
    "# # refer 链接：https://leetcode.cn/problems/find-the-index-of-the-large-integer/\n",
    "class Solution:\n",
    "\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "\n",
    "        n = reader.length()\n",
    "\n",
    "        L = 0               #实指\n",
    "\n",
    "        R = n - 1           #实指\n",
    "\n",
    "        while L < R :\n",
    "\n",
    "            mid = L + R >> 1\n",
    "\n",
    "            #-------------- 奇数个，L=0 [0 1 2] mid=3 [3 4 5 6] R=6\n",
    "\n",
    "            if (R - L) % 2 == 0:\n",
    "\n",
    "                #比较 [0 1 2] 和 [4 5 6]\n",
    "\n",
    "                check = reader.compareSub(L, mid - 1, mid + 1 , R)\n",
    "\n",
    "                #-- 左边大，在左\n",
    "\n",
    "                if check == 1:\n",
    "\n",
    "                    R = mid - 1     #左半的R界为mid=2\n",
    "\n",
    "                #-- 右边大，在右\n",
    "\n",
    "                elif check == -1:\n",
    "\n",
    "                    L = mid + 1     #右半的L界为4\n",
    "\n",
    "                #-- 两边一样大\n",
    "\n",
    "                else:\n",
    "\n",
    "                    return mid\n",
    "\n",
    "\n",
    "\n",
    "            #--------------偶数个，L=0 [0 1 2] mid=2 [3 4 5] R=5\n",
    "\n",
    "            else:\n",
    "\n",
    "                #-- 比较 [0 1 2] 和 [3 4 5]\n",
    "\n",
    "                check = reader.compareSub(L, mid, mid + 1, R)\n",
    "\n",
    "                #-- 左边大，在左\n",
    "\n",
    "                if check == 1:\n",
    "\n",
    "                    R = mid         #左半的R界为2\n",
    "\n",
    "                #-- 右边大，在右\n",
    "\n",
    "                elif check == -1:\n",
    "\n",
    "                    L = mid + 1     #右半的L界为3\n",
    "\n",
    "                #-- 两边一样大，不存在\n",
    "\n",
    "                else:\n",
    "\n",
    "                    return -1\n",
    "\n",
    "        return L\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        l, r = 0, reader.length() - 1\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "            if (l + r) % 2 == 0:\n",
    "                result = reader.compareSub(l, m - 1, m + 1, r) \n",
    "                if result == 0:\n",
    "                    return m\n",
    "                elif result == 1:\n",
    "                    r = m - 1\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            else:\n",
    "                result = reader.compareSub(l, m, m + 1, r) \n",
    "                if result == 1:\n",
    "                    r = m \n",
    "                else:\n",
    "                    l = m + 1\n",
    "        return l\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        l, r = 0, n - 1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            IsOdd = (r - l + 1) % 2 == 1\n",
    "            if IsOdd:  #区间长度为奇数\n",
    "                ans = reader.compareSub(l, mid, mid, r)\n",
    "            else:\n",
    "                ans = reader.compareSub(l, mid, mid + 1, r)\n",
    "            if ans == 0:\n",
    "                return mid\n",
    "            elif ans > 0:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        l,r = 0, reader.length()-1\n",
    "        while l < r:\n",
    "            mid = (l+r)//2\n",
    "            if (r-l+1)&1:\n",
    "                comp = reader.compareSub(l, mid-1, mid+1, r)\n",
    "                if comp == 1:\n",
    "                    r = mid - 1\n",
    "                elif comp == 0:\n",
    "                    return mid \n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            else:\n",
    "                comp = reader.compareSub(l, mid, mid+1, r)\n",
    "                if comp == 1:\n",
    "                    r = mid \n",
    "                else:\n",
    "                    l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        left = 0\n",
    "        right = reader.length() - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            even = (left + right) % 2\n",
    "            if even == 0:\n",
    "                temp = reader.compareSub(left, mid-1, mid+1, right)\n",
    "            else:\n",
    "                temp = reader.compareSub(left, mid, mid+1, right)\n",
    "            if temp > 0:\n",
    "                right = mid\n",
    "            elif temp < 0:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                return mid\n",
    "\n",
    "        return left \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        left, right = 0, reader.length() - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            cur_l = right - left + 1\n",
    "            if cur_l % 2 == 0:\n",
    "                if reader.compareSub(left, mid, mid + 1, right) < 0:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            else:\n",
    "                if reader.compareSub(left, mid, mid, right) < 0:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "        return left\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length() \n",
    "        l, y = 0, n - 1\n",
    "        while l < y:\n",
    "            r = (l + y) // 2\n",
    "            x = y - (r - l)\n",
    "            cmpret = reader.compareSub(l, r, x, y)\n",
    "            if cmpret == 0:\n",
    "                return r\n",
    "            if cmpret == 1:\n",
    "                l, y = l, r\n",
    "            if cmpret == -1:\n",
    "                l, y = x, y\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        left, right = 0, n - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            odd = (right - left + 1) % 2 == 1\n",
    "            compare_sub = reader.compareSub(left, mid, mid, right) if odd else reader.compareSub(left, mid, mid+1, right)\n",
    "            if compare_sub < 0:\n",
    "                left = mid if odd else mid + 1\n",
    "            elif compare_sub > 0:\n",
    "                right = mid\n",
    "            else:\n",
    "                return mid\n",
    "\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        l,r = 0, reader.length()-1\n",
    "        while l < r:\n",
    "            mid = (l+r)//2\n",
    "            if (r-l+1)&1:\n",
    "                comp = reader.compareSub(l, mid-1, mid+1, r)\n",
    "                if comp == 1:\n",
    "                    r = mid - 1\n",
    "                elif comp == 0:\n",
    "                    return mid \n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            else:\n",
    "                comp = reader.compareSub(l, mid, mid+1, r)\n",
    "                if comp == 1:\n",
    "                    r = mid \n",
    "                else:\n",
    "                    l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        l, r = 0, n-1\n",
    "        while l<=r:\n",
    "            if (r-l+1)%2 == 0: #偶数 [l, mid] [mid+1,r]\n",
    "                mid = (l+r)//2\n",
    "                sign = reader.compareSub(l, mid, mid+1, r)\n",
    "                if sign == 1:\n",
    "                    r = mid\n",
    "                elif sign == -1:\n",
    "                    l = mid + 1\n",
    "            else: #奇数 [l, mid-1] mid [mid + 1, r]\n",
    "                mid = (l+r)//2\n",
    "                if l == r:\n",
    "                    return l\n",
    "                sign = reader.compareSub(l, mid-1, mid+1, r)\n",
    "                if sign == 1:\n",
    "                    r = mid-1\n",
    "                elif sign == -1:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    return mid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        l,r = 0, reader.length()-1\n",
    "        while l < r:\n",
    "            mid = (l+r)//2\n",
    "            if (r-l+1)%2:\n",
    "                comp = reader.compareSub(l, mid-1, mid+1, r)\n",
    "                if comp == 1:\n",
    "                    r = mid - 1\n",
    "                elif comp == 0:\n",
    "                    return mid \n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            else:\n",
    "                comp = reader.compareSub(l, mid, mid+1, r)\n",
    "                if comp == 1:\n",
    "                    r = mid \n",
    "                else:\n",
    "                    l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        l,r = 0, reader.length()-1\n",
    "        while l < r:\n",
    "            mid = (l+r)>>1\n",
    "            is_odd = (r-l+1)&1 == 1\n",
    "            if is_odd:\n",
    "                comp = reader.compareSub(l, mid-1, mid+1, r)\n",
    "                if comp == 1:\n",
    "                    r = mid - 1\n",
    "                elif comp == 0:\n",
    "                    return mid \n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            else:\n",
    "                comp = reader.compareSub(l, mid, mid+1, r)\n",
    "                if comp == 1:\n",
    "                    r = mid \n",
    "                else:\n",
    "                    l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        lt, rt = 0, n - 1\n",
    "\n",
    "        while lt < rt:\n",
    "            mid = (lt + rt)//2\n",
    "            if (lt + rt)%2 == 0:\n",
    "                res = reader.compareSub(lt, mid - 1, mid + 1, rt)\n",
    "                if res == 0:\n",
    "                    return mid\n",
    "                elif res == 1:\n",
    "                    rt = mid - 1\n",
    "                else:\n",
    "                    lt = mid + 1\n",
    "            else:\n",
    "                res = reader.compareSub(lt, mid, mid + 1, rt)\n",
    "                if res == 1:\n",
    "                    rt = mid\n",
    "                else:\n",
    "                    lt = mid + 1\n",
    "        \n",
    "        return lt\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        l, r = 0, reader.length()-1\n",
    "        while l<=r:\n",
    "            if (r-l+1)%2 == 0: #偶数 [l, mid] [mid+1,r]\n",
    "                mid = (l+r)//2\n",
    "                sign = reader.compareSub(l, mid, mid+1, r)\n",
    "                if sign == 1:\n",
    "                    r = mid\n",
    "                elif sign == -1:\n",
    "                    l = mid + 1\n",
    "            else: #奇数 [l, mid-1] mid [mid + 1, r]\n",
    "                mid = (l+r)//2\n",
    "                if l == r:\n",
    "                    return l\n",
    "                sign = reader.compareSub(l, mid-1, mid+1, r)\n",
    "                if sign == 1:\n",
    "                    r = mid-1\n",
    "                elif sign == -1:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    return mid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        i, j = 0, reader.length() - 1\n",
    "        while i < j:\n",
    "            m = (i + j) // 2\n",
    "            if (i + j) % 2:\n",
    "                res = reader.compareSub(i, m, m + 1, j)\n",
    "                if res == 1:\n",
    "                    j = m\n",
    "                else:\n",
    "                    i = m + 1\n",
    "            else:\n",
    "                res = reader.compareSub(i, m - 1, m + 1, j)\n",
    "                if res == 1:\n",
    "                    j = m - 1\n",
    "                elif res == -1:\n",
    "                    i = m + 1\n",
    "                else:\n",
    "                    return m\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        l,r = 0, reader.length()-1\n",
    "        while l < r:\n",
    "            mid = (l+r)//2\n",
    "            if (r-l+1)%2:\n",
    "                comp = reader.compareSub(l, mid-1, mid+1, r)\n",
    "                if comp == 1:\n",
    "                    r = mid - 1\n",
    "                elif comp == 0:\n",
    "                    return mid \n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            else:\n",
    "                comp = reader.compareSub(l, mid, mid+1, r)\n",
    "                if comp == 1:\n",
    "                    r = mid \n",
    "                else:\n",
    "                    l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        i, j = 0, reader.length()-1\n",
    "        while i < j:\n",
    "            mid = i + (j-i)//2\n",
    "            if (j-i+1) % 2 == 0:\n",
    "                res = reader.compareSub(i, mid, mid+1, j)\n",
    "            else:\n",
    "                res = reader.compareSub(i, mid, mid, j)\n",
    "            if res == -1:\n",
    "                i = mid + 1\n",
    "            else:\n",
    "                j = mid\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        l = 0\n",
    "        r = reader.length() - 1\n",
    "        while l < r:\n",
    "            flag = (r - l + 1) % 2\n",
    "            mid = l + (r - l) // 2\n",
    "            if flag == 0:\n",
    "                checker = reader.compareSub(l, mid, mid + 1, r)\n",
    "                if checker == 1:\n",
    "                    r = mid\n",
    "                elif checker == -1:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    return -1\n",
    "            else:\n",
    "                checker = reader.compareSub(l, mid - 1, mid + 1, r)\n",
    "                if checker == 1:\n",
    "                    r = mid - 1\n",
    "                elif checker == -1:\n",
    "                    l = mid + 1  \n",
    "                else:\n",
    "                    return mid\n",
    "        return l\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length() \n",
    "        l, y = 0, n - 1\n",
    "        while l < y:\n",
    "            r = (l + y) // 2\n",
    "            x = y - (r - l)\n",
    "            cmpret = reader.compareSub(l, r, x, y)\n",
    "            if cmpret == 0:\n",
    "                return r\n",
    "            if cmpret == 1:\n",
    "                y = r\n",
    "            elif cmpret == -1:\n",
    "                l = x\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # # 二分查找\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        i = 0\n",
    "        j = n - 1\n",
    "        while i < j - 1:\n",
    "            mid = (i + j) // 2\n",
    "            if (j - i) % 2:\n",
    "                a, b, x, y = i, mid, mid + 1, j\n",
    "            else:\n",
    "                a, b, x, y = i, mid, mid, j\n",
    "\n",
    "            res = reader.compareSub(a, b, x, y)\n",
    "            if res == 1:\n",
    "                i, j = a, b\n",
    "            elif res == -1:\n",
    "                i, j = x, y\n",
    "            else:\n",
    "                return mid\n",
    "\n",
    "        if reader.compareSub(i, i, j, j) == 1:\n",
    "            return i\n",
    "\n",
    "        return j\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        len = reader.length()\n",
    "        left = 0\n",
    "        right = len - 1\n",
    "        half = 0\n",
    "        comp = 0\n",
    "        temp = 0\n",
    "        while len > 0:\n",
    "            len = right - left + 1\n",
    "            half = len // 2\n",
    "            if len % 2 == 0:\n",
    "                comp = 1\n",
    "            else:\n",
    "                comp = 0\n",
    "            temp = reader.compareSub(left, left + half - comp, left + half, right)\n",
    "            if temp == 0:\n",
    "                return left + half - comp\n",
    "            elif temp == 1:\n",
    "                right = left + half - comp\n",
    "            elif temp == -1:\n",
    "                left = left + half\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        half = 0\n",
    "        comp = 0\n",
    "        temp = 0\n",
    "        while n > 0:\n",
    "            n = right - left + 1\n",
    "            half = n // 2\n",
    "            if n % 2 == 0:\n",
    "                comp = 1\n",
    "            else:\n",
    "                comp = 0\n",
    "            temp = reader.compareSub(left, left + half - comp, left + half, right)\n",
    "            if temp == 0:\n",
    "                return left + half - comp\n",
    "            elif temp == 1:\n",
    "                right = left + half - comp\n",
    "            elif temp == -1:\n",
    "                left = left + half\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        len = reader.length()\n",
    "        left = 0\n",
    "        right = len - 1\n",
    "        half = 0\n",
    "        comp = 0\n",
    "        temp = 0\n",
    "        while len > 0:\n",
    "            len = right - left + 1\n",
    "            half = len // 2\n",
    "            if len % 2 == 0:\n",
    "                comp = 1\n",
    "            else:\n",
    "                comp = 0\n",
    "            temp = reader.compareSub(left, left + half - comp, left + half, right)\n",
    "            if temp == 0:\n",
    "                return left + half - comp\n",
    "            elif temp == 1:\n",
    "                right = left + half - comp\n",
    "            elif temp == -1:\n",
    "                left = left + half\n",
    "        return 0\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        i = 0\n",
    "        j = reader.length()\n",
    "        while i + 1 < j:\n",
    "            x = (j - i) // 2\n",
    "            r = reader.compareSub(i, i+x-1, j-x, j-1)\n",
    "            if r > 0:\n",
    "                j = i + x\n",
    "            elif r < 0:\n",
    "                i = j - x\n",
    "            else:\n",
    "                return i+x\n",
    "        return i\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "\n",
    "        left, right = 0, n - 1\n",
    "\n",
    "        while right > left:\n",
    "            k = right - left + 1\n",
    "            if k % 2 == 0:\n",
    "                l, r = left, left + k // 2 - 1\n",
    "                x, y = left + k // 2, right\n",
    "                com = reader.compareSub(l, r, x, y)\n",
    "                if com == 1:\n",
    "                    left, right = l, r\n",
    "                else:\n",
    "                    left, right = x, y\n",
    "            else:\n",
    "                l, r = left, left + k // 2 - 1\n",
    "                x, y = left + k // 2, right - 1\n",
    "                com = reader.compareSub(l, r, x, y)\n",
    "                if com == 0:\n",
    "                    return right\n",
    "                elif com == 1:\n",
    "                    left, right = l, r\n",
    "                else:\n",
    "                    left, right = x, y\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        l, r = 0, reader.length()-1\n",
    "        while l<=r:\n",
    "            if (r-l+1)%2 == 0: #偶数 [l, mid] [mid+1,r]\n",
    "                mid = (l+r)//2\n",
    "                sign = reader.compareSub(l, mid, mid+1, r)\n",
    "                if sign == 1:\n",
    "                    r = mid\n",
    "                elif sign == -1:\n",
    "                    l = mid + 1\n",
    "            else: #奇数 [l, mid-1] mid [mid + 1, r]\n",
    "                mid = (l+r)//2\n",
    "                if l == r:\n",
    "                    return l\n",
    "                sign = reader.compareSub(l, mid-1, mid+1, r)\n",
    "                if sign == 1:\n",
    "                    r = mid-1\n",
    "                elif sign == -1:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    return mid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        low = 0\n",
    "        high = n - 1\n",
    "        while low < high:\n",
    "            mid = low + (high - low) // 2\n",
    "            if 2 * mid != high + low:\n",
    "                score = reader.compareSub(low, mid, mid+1, high)\n",
    "                print(low, mid, mid+1, high, ' * ', score)\n",
    "                if score == 1:\n",
    "                    high = mid\n",
    "                else:\n",
    "                    low = mid + 1\n",
    "            else:\n",
    "                score = reader.compareSub(low, mid-1, mid+1, high)\n",
    "                print(low, mid-1, mid+1, high, ' * ', score)\n",
    "                if score == 1:\n",
    "                    high = mid - 1\n",
    "                elif score == 0:\n",
    "                    return mid\n",
    "                else:\n",
    "                    low = mid + 1\n",
    "        return low\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        \n",
    "        start, end = 0, reader.length() - 1\n",
    "        while start < end - 1:\n",
    "            is_even = (end - start + 1) % 2 == 0\n",
    "            mid = int(start + (end - start) / 2)\n",
    "            \n",
    "            if is_even:\n",
    "                compare_res = reader.compareSub(start, mid, mid + 1, end)\n",
    "                if compare_res == 0:\n",
    "                    return -1\n",
    "                elif compare_res == 1:\n",
    "                    end = mid\n",
    "                else:\n",
    "                    start = mid + 1\n",
    "            else:\n",
    "                compare_res = reader.compareSub(start, mid - 1, mid + 1, end)\n",
    "                if compare_res == 0:\n",
    "                    return mid\n",
    "                elif compare_res == 1:\n",
    "                    end = mid - 1\n",
    "                else:\n",
    "                    start = mid + 1\n",
    "        \n",
    "        compare_res = reader.compareSub(start, start, end, end)\n",
    "        if start == end:\n",
    "            return start\n",
    "        \n",
    "        if compare_res == 0:\n",
    "            return -1\n",
    "        elif compare_res == 1:\n",
    "            return start\n",
    "        else:\n",
    "            return end\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        #解题思路：\n",
    "        #arr中只有两个元素，且最大的元素只出现一次\n",
    "        #首先调用，知道最大的元素/最小的元素\n",
    "        #从中间切分，两段加和即可\n",
    "\n",
    "        n = reader.length()\n",
    "        l,r = 0,n - 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if (r - l + 1) % 2 == 0: #区间长度为偶数\n",
    "                cur = reader.compareSub(l,mid,mid + 1,r)\n",
    "                if cur == 1:\n",
    "                    r = mid\n",
    "                elif cur == -1:\n",
    "                    l = mid + 1\n",
    "            else:\n",
    "                cur = reader.compareSub(l,mid - 1,mid + 1,r)\n",
    "                if cur == 1:\n",
    "                    r = mid - 1\n",
    "                elif cur == -1:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    return mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n=reader.length()\n",
    "        l,r=0,n-1\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if (r+1-l)%2:\n",
    "                ll,rr,x,y=l,mid-1,mid+1,r \n",
    "            else:\n",
    "                ll,rr,x,y=l,mid,mid+1,r\n",
    "            cmp=reader.compareSub(ll,rr,x,y)\n",
    "            if (r+1-l)%2 and cmp==0:\n",
    "                return mid \n",
    "            elif cmp==1:\n",
    "                r=rr    \n",
    "            elif cmp==-1:\n",
    "                l=x \n",
    "        return l\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        i = 0\n",
    "        j = n - 1\n",
    "        while i < j - 1:\n",
    "            mid = i + (j - i) // 2\n",
    "            if (j - i) % 2:\n",
    "                a, b, x, y = i, mid, mid + 1, j\n",
    "            else:\n",
    "                a, b, x, y = i, mid, mid, j\n",
    "            res = reader.compareSub(a, b, x, y)\n",
    "            if res == 1:\n",
    "                i, j = a, b\n",
    "            elif res == -1:\n",
    "                i, j = x, y \n",
    "            else:\n",
    "                return mid \n",
    "        if reader.compareSub(i, i, j, j) == 1:\n",
    "            return i \n",
    "        return j\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        l = 0\n",
    "        r = reader.length() - 1\n",
    "        while l < r:\n",
    "            flag = (r - l + 1) % 2\n",
    "            mid = l + (r - l) // 2\n",
    "            if flag == 0:\n",
    "                checker = reader.compareSub(l, mid, mid + 1, r)\n",
    "                if checker == 1:\n",
    "                    r = mid\n",
    "                elif checker == -1:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    return -1\n",
    "            else:\n",
    "                checker = reader.compareSub(l, mid - 1, mid + 1, r)\n",
    "                if checker == 1:\n",
    "                    r = mid - 1\n",
    "                elif checker == -1:\n",
    "                    l = mid + 1  \n",
    "                else:\n",
    "                    return mid\n",
    "        return l\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        # print(n)\n",
    "        left, right = 0, n-1\n",
    "        while left < right:\n",
    "            mid = (right+left)//2\n",
    "            # print(left, right, mid)\n",
    "            if (right-left)%2 == 0:\n",
    "                l, r, x, y = left, mid, mid, right\n",
    "            else:\n",
    "                l, r, x, y = left, mid, mid+1, right\n",
    "            # print(reader.compareSub(left, left+num, right-num, right))\n",
    "            res = reader.compareSub(l, r, x, y)\n",
    "            if res == 1:\n",
    "                right = r\n",
    "            elif res == 0:\n",
    "                return mid\n",
    "            else:\n",
    "                left = x\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        left, right = 0, reader.length()-1\n",
    "        while left<=right:\n",
    "            if right-left<2:\n",
    "                return left if reader.compareSub(left,left,right,right)==1 else right\n",
    "            (r, x) = ((left+right)//2, (left+right)//2+1) if (left+right)%2==1 else ((left+right)//2-1, (left+right)//2+1)\n",
    "            status = reader.compareSub(left,r,x,right)\n",
    "            print(left,r,x,right,status)\n",
    "            if status==1:\n",
    "                right = r \n",
    "            elif status==-1:\n",
    "                left = x \n",
    "            else:\n",
    "                return r+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        left, right = 0, reader.length()-1\n",
    "        while left<=right:\n",
    "            if right-left<2:\n",
    "                return left if reader.compareSub(left,left,right,right)==1 else right\n",
    "            (r, x) = ((left+right)//2, (left+right)//2+1) if (left+right)%2==1 else ((left+right)//2-1, (left+right)//2+1)\n",
    "            status = reader.compareSub(left,r,x,right)\n",
    "            print(left,r,x,right,status)\n",
    "            if status==1:\n",
    "                right = r \n",
    "            elif status==-1:\n",
    "                left = x \n",
    "            else:\n",
    "                return r+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        l, r = 0, n - 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            \n",
    "            if (r-l) % 2 == 0:\n",
    "                print(l, mid - 1, mid + 1, r)\n",
    "                comp = reader.compareSub(l, mid - 1, mid + 1, r)\n",
    "                if comp == 0:\n",
    "                    return mid\n",
    "                elif comp == 1:\n",
    "                    r = mid - 1\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            else:\n",
    "                print(l, mid, mid + 1, r)\n",
    "                comp = reader.compareSub(l, mid, mid + 1, r)\n",
    "                if comp == 1:\n",
    "                    r = mid\n",
    "                elif comp == -1:\n",
    "                    l = mid + 1\n",
    "        \n",
    "        return l\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        left, right = 0, n - 1\n",
    "        while left <= right: \n",
    "            mid = left + (right - left) // 2\n",
    "            odd = (right - left + 1) % 2 == 1\n",
    "            print(left, mid, right)\n",
    "            compare = reader.compareSub(left, mid, mid if odd else mid + 1, right) \n",
    "            if compare > 0:\n",
    "                right = mid \n",
    "            elif compare < 0:\n",
    "                left = mid if odd else mid + 1  \n",
    "            else:\n",
    "                return mid \n",
    "\n",
    "    # def getIndex(self, reader):\n",
    "    #     length = reader.length()\n",
    "    #     left, right = 0, length - 1\n",
    "    #     while left <= right:\n",
    "    #         mid = left + (right - left) // 2\n",
    "    #         odd = (right - left + 1) % 2 == 1\n",
    "    #         compareSub = reader.compareSub(left, mid, mid if odd else mid + 1, right)\n",
    "    #         if compareSub < 0:\n",
    "    #             left = mid if odd else mid + 1 \n",
    "    #         elif compareSub > 0:\n",
    "    #             right = mid\n",
    "    #         else:\n",
    "    #             return mid\n",
    "\n",
    "    #     return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares the sum of arr[l..r] with the sum of arr[x..y]\n",
    "#\t # return 1 if sum(arr[l..r]) > sum(arr[x..y])\n",
    "#\t # return 0 if sum(arr[l..r]) == sum(arr[x..y])\n",
    "#\t # return -1 if sum(arr[l..r]) < sum(arr[x..y])\n",
    "#    def compareSub(self, l: int, r: int, x: int, y: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        left, right = 0, n - 1\n",
    "        while left <= right: \n",
    "            mid = left + (right - left) // 2\n",
    "            odd = (right - left + 1) % 2 == 1\n",
    "            print(left, mid, right)\n",
    "            compare = reader.compareSub(left, mid, mid if odd else mid + 1, right) \n",
    "            if compare > 0:\n",
    "                right = mid \n",
    "            elif compare < 0:\n",
    "                left = mid if odd else mid + 1  \n",
    "            else:\n",
    "                return mid \n",
    "                \n",
    "    # def getIndex(self, reader):\n",
    "    #     length = reader.length()\n",
    "    #     left, right = 0, length - 1\n",
    "    #     while left <= right:\n",
    "    #         mid = left + (right - left) // 2\n",
    "    #         odd = (right - left + 1) % 2 == 1\n",
    "    #         compareSub = reader.compareSub(left, mid, mid if odd else mid + 1, right)\n",
    "    #         if compareSub < 0:\n",
    "    #             left = mid if odd else mid + 1 \n",
    "    #         elif compareSub > 0:\n",
    "    #             right = mid\n",
    "    #         else:\n",
    "    #             return mid\n",
    "\n",
    "    #     return 0\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
